1. Field Of The Invention
The present invention is generally related to a tag data processing apparatus (hereinafter referred to simply as a data processing apparatus), and more particularly to a data processing apparatus used for a data flow computer utilizing a tagged token scheme.
2. Description Of The Related Art
FIG. 6 is a data flow diagram showing a compiled program of C=(A+B)*(A-B). Respective nodes correspond to instructions of the data flow computer. The data are carried on tokens which flow on arcs connecting the nodes. Each arc is a first in-first out queue and can hold an unbounded number of tokens.
When the subroutine program in FIG. 6 is called and parallel-executed by two different master programs (P, Q) at the same time, two kinds of tokens corresponding to the two master programs P and Q exist on the same arc of the data flow diagram of FIG. 6. In order to execute each operation without confusion under the above-mentioned condition, a method known as a tagged token scheme is used. Each token is added with an environment identifier (tag) indicating which master program calls the subroutine program. In a tagged token scheme, a group of tokens having the same tag are matched together as one operand and processed.
In order to efficiently realize the tagged token control scheme in a data flow computer, a data processing apparatus is provided for adding the tag, for renewing or reinitializing a used tag and for storing a tag capable of being used.
The conventional data processing apparatus is described as follows.
FIG. 7 is a block diagram showing an example of a conventional data processing apparatus which uses a tag managing table (for example, Japanese patent unexamined patent application No. Sho 59-27352).
In FIG. 7, a tag table memory 5 stores a tag capable of being used. The tag table memory 5 comprises a tag field and empty/full indication field. Reading and writing of the tag table memory 5 are executed using the contents of an address register 4.
The tag adding process is described as follows. A receiving data register 1 receives a tag adding instruction in a conventional manner. A sequence controller 2 decodes the content of the receiving data register 1. When the content corresponds to a tag add request, the sequence controller 2 executes a so called hash function using the tag field value of the content as a key. The hash function also utilizes an operation/test circuit 3 and temporary data register 8.
The hash function is a well known method for distributing data more or less randomly over a number of different addresses. Once the hash function is executed, the result is written in the address register 4. The tag memory table 5 is read according to the content of the address register 4.
It can be determined whether the tag in the address is usable (empty) or being used (full) by examining the empty/full indication field. When the empty/full indication field is full, another address is searched in accordance with, for example, an open hash method or chain method for detecting an empty tag. When the empty tag is detected, the content of the address register 4 is written in a tag field of a transmitting data register 6 in order to associate a new tag to the address detected as having an empty tag. The other field of the transmitting data register 6 is written with the content of the receiving data register 1.
The following operation is executed as a post processing operation. The sequence controller 2 performs an edit function combining the tag and the empty/full indication field (the bit of which is full), and writes it in the tag table memory 5, thereby completing the operation for the tag adding instruction.
The used-tag-restoring process is described as follows. When the receiving data register 1 receives the tag restoring instruction issued from another apparatus, the sequence controller 2 decodes the contents of the receiving data register 1. If the sequence controller 2 recognizes the tag restoring request, the content of the tag field of the receiving data register 1 is written to the address register 4. The content of the tag table memory 5 is read in accordance with the address, and the detected tag field value is written to the tag field of the transmitting data register 6. With respect to content other than the tagged field, the content of the receiving data register 1 is written as it is.
Then, the following post-processing process is executed. The sequence controller 2 causes the operation/test circuit 3 to issue all zero data and writes the zero data to the empty/full field and the tag field of the tag memory 5 in accordance with the addresses in the address register 4. Thus, the tag restoring instruction is completed.
In a conventional data processing apparatus, the architecture is complicated since both the operation/test circuit 3 and the sequence controller 2 etc. are needed. Further, the manipulation with regard to address register 4 and the tag table memory 5 is troublesome. The processing is made sequentially by means of the sequence controller 2, and therefore excessive processing time is needed for adding tags and for restoring tags. Accordingly, a data flow computer using a conventional data processing apparatus is difficult to execute at high speed operation.